package seqlist;

/**
 * @Author: yuisama
 * @Date: 2019/12/9 16:04
 * @Description:
 */

class DoubleNode {
    int val;
    DoubleNode prev;
    DoubleNode next;

    public DoubleNode(DoubleNode prev,int val,DoubleNode next) {
        this.val = val;
        this.prev = prev;
        this.next = next;
    }
}

public class DoubleLinkedList {
    private int size;
    private DoubleNode head;
    private DoubleNode last;

    public void add(int data) {
        addLast(data);
    }

    public void addFirst(int data) {
        DoubleNode node = new DoubleNode(null,data,head);
        if (size == 0) {
            head = last = node;
            size ++;
            return;
        }
        head.prev = node;
        head = node;
        size ++;
    }

    public void addLast(int data) {
        DoubleNode node = new DoubleNode(last,data,null);
        if (size == 0) {
            head = last = node;
            size ++;
            return;
        }
        last.next = node;
        last = node;
        size ++;
    }

    public void addIndex(int index,int data) {
        if (index < 0 || index > size) {
            System.out.println("索引非法!");
            return;
        }else if (index == 0) {
            addFirst(data);
        }else if (index == size) {
            addLast(data);
        }else {
            // 找到index的前驱节点
            DoubleNode prev = node(index - 1);
            DoubleNode node = new DoubleNode(prev,data,prev.next);
            prev.next.prev = node;
            prev.next = node;
            size ++;
        }
    }

    /**
     * 删除第一个值为data的节点
     * @param data
     */
    public void remove(int data) {
        DoubleNode x = head;
        while (x != null) {
            if (x.val == data) {
                unlink(x);
                return;
            }
            x = x.next;
        }
    }

    /**
     * 删除所有值为data的节点
     * @param data
     */
    public void removeAll(int data) {
        for(DoubleNode x = head;x != null;) {
            if (x.val == data) {
                DoubleNode temp = x.next;
                unlink(x);
                x = temp;
            }else {
                x = x.next;
            }
        }
    }

    public int get(int index) {
        if (!rangeCheck(index)) {
            return -1;
        }
        return node(index).val;
    }

    public boolean contains(int data) {
        DoubleNode temp = head;
        for (int i = 0; i < size; i++) {
            if (temp.val == data) {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    public int set(int index,int data) {
        if (!rangeCheck(index)) {
            return -1;
        }
        DoubleNode node = node(index);
        int oldVal = node.val;
        node.val = data;
        return oldVal;
    }

    public void clear() {
        while (head != null) {
            DoubleNode temp = head;
            head = head.next;
            temp.prev = temp.next = null;
            temp.val = 0;
            size --;
        }
    }

    public int size() {
        return size;
    }

    public void print() {
        for (DoubleNode x = head;x != null;x = x.next) {
            System.out.print(x.val +"、");
        }
        System.out.println();
    }

    private DoubleNode node(int index) {
        DoubleNode result = null;
        if (index < (size >> 1)) {
            result = head;
            for (int i = 0; i < index; i++) {
                result = result.next;
            }
        }else {
            result = last;
            for (int i = size - 1; i > index; i--) {
                result = result.prev;
            }
        }
        return result;
    }

    private boolean rangeCheck(int index) {
        if (index < 0 || index >= size){
            System.out.println("索引非法!");
            return false;
        }
        return true;
    }

    private void unlink(DoubleNode node) {
        DoubleNode prev = node.prev;
        DoubleNode next = node.next;

        if (prev == null) {
            head = next;
        }else {
            prev.next = next;
            node.prev = null;
        }

        if (next == null) {
            last = prev;
        }else {
            next.prev = prev;
            node.next = null;
        }

        node.val = 0;
        size --;
    }

}
